package com.zhouyong.leetcode.回文链表234;

import com.zhouyong.leetcode.ListNode;

import java.util.ArrayList;

/**
 * @Author 99
 * @Date 2022/9/25 15:31
 * @Version 1.0
 */
public class Test {

    // 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
    // 输入：head = [1,2,2,1]
    // 输出：true
    public static void main(String[] args) {
        ListNode node = new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(1, null))));
        System.out.println(isPalindrome(node));
    }

    public static boolean isPalindrome(ListNode head) {
        // 如果反转链表的结果还是和原始链表一致说明这个链表是回文链表
        // 执行用时：5 ms，在所有 Java 提交中击败了62.62%的用户
        // 内存消耗：56.6 MB, 在所有 Java 提交中击败了63.58%的用户
//        ListNode resultNode = null;
//        ListNode oldHead = head;
//        for (ListNode a = head; a != null; a = a.next) {
//            resultNode = new ListNode(a.val, resultNode);
//        }
//        while (oldHead != null) {
//            if (oldHead.val != resultNode.val) {
//                return false;
//            }
//            oldHead = oldHead.next;
//            resultNode = resultNode.next;
//        }
//        return true;

        // 将链表的数据放到数组中然后再使用双指针
        // 执行用时：8 ms, 在所有 Java 提交中击败了37.11%的用户
        // 内存消耗：53.3 MB, 在所有 Java 提交中击败了85.20%的用户
        ArrayList<Integer> list = new ArrayList<>();
        while (null != head) {
            list.add(head.val);
            head = head.next;
        }
        int first = 0, end = list.size() - 1;
        boolean flag = Boolean.TRUE;
        while (end > first) {
            flag = flag && list.get(first).equals(list.get(end));
            first++;
            end--;
        }
        return flag;
    }
}
